#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100005;
const int maxm = 200005;

int head[maxn],num_edge,n,m,s;
int d[maxn];
bool vis[maxn];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;

struct node{
	int next,to,dis;
}edge[maxm];

int read(){
	char c;int x=0;int f=1;

	while(!isdigit(c=getchar())){
		if(c=='-')f=-1;
	}
	x=c-'0';
	while(isdigit(c=getchar())){
		x=x*10+c-'0';
	}
	return x*f;
}

void add_edge(int from,int to,int dis){
	num_edge++;
	edge[num_edge].next=head[from];
	edge[num_edge].to=to;
	edge[num_edge].dis=dis;
	head[from]=num_edge;
}

void dji(){
	for(int i=1;i<=n;i++)d[i]=1919260817;
	d[s]=0;
	q.push(make_pair(d[s],s));
	while(!q.empty()){
		pii tmp=q.top();
		q.pop();
		int u=tmp.second;
		if(vis[u])continue;
		else{
			vis[u]=true;
			for(int i=head[u];i!=0;i=edge[i].next){
				int v=edge[i].to;
				int w=edge[i].dis;
				if(d[v]>d[u]+w){
					d[v]=d[u]+w;
					q.push(make_pair(d[v],v));
				}
			}
		}
	}
}

int main(){
	n=read();m=read();s=read();
	int x,y,z;
	for(int i=1;i<=m;i++){
		x=read();y=read();z=read();
		add_edge(x,y,z);
	}
	dji();
	for(int i=1;i<=n;i++)printf("%d ",d[i]);
	return 0;
}

